Jeder Teilgraph eines Graphen G, der dieselbe Knotenmenge wie G besitzt und ein Baum ist, heißt spannender Baum von G. Unter allen spannenden Bäumen von G wird derjenige als minimaler spannender Baum bezeichnet, dessen Summe der Kanten- bzw. Pfeilbewertungen minimal ist. Minimale spannende Bäume sin